/* COMPLEJIDADES (NOTACION)
 * E = cant de tramos = cant de aristas
 * V = cant de ciudades = cant de vertices
 */
package uba.algo3.tp2.ej1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;

public class Maximo {
			
		private HashMap<String, Ciudad> adyacencias= new HashMap<String, Ciudad>();
		private PriorityQueueExt noVistos; //ciudades no vistas aun
		
		public int obtenerMaximo(String ciudadOrigen, String ciudadDestino, ArrayList<String> amistadesLista) { 
			
			generarCiudades(ParseAVecinos(amistadesLista)); //O(E)
			
			adyacencias.get(ciudadOrigen).cambiarPesoHastaAqui(Integer.MAX_VALUE); //O(1)
			
			noVistos = new PriorityQueueExt<Ciudad>(adyacencias.values()); //O(V*logV)

			while(!noVistos.isEmpty()){ //Se ejecuta V veces
			
				Ciudad ciudad = (Ciudad) (noVistos.poll()); //O(log V)
				System.out.println("Proximo Maximo: " + ciudad);
			
				HashSet<Arista> adyCiudadActual = ciudad.obtenerAdy(); //O(1)
				
				for (Arista adyActual : adyCiudadActual) { 
					//Me fijo, sabiendo cuanto podia cargar hasta el nodo k, cuanto puedo cargar ahora de k al adyActual
					int minimo = Math.min(ciudad.obtenerPesoHastaAqui(), adyActual.obtenerPesoTolerado());	
					
					if(adyacencias.get(adyActual.obtenerNombreAdyacente()).obtenerPesoHastaAqui() < minimo){
						adyacencias.get(adyActual.obtenerNombreAdyacente()).cambiarPesoHastaAqui(minimo);
					    //Actualizar en el heap la prioridad del adyacente:
							int pesoNuevo = adyacencias.get(adyActual.obtenerNombreAdyacente()).obtenerPesoHastaAqui(); 
						 	noVistos.incrementarPrioridad(adyActual.obtenerNombreAdyacente(),pesoNuevo); 
					}
					//Sacar 'ciudad' de los adyacentes al adyActual:
					HashSet<Arista> adyAdyActual = adyacencias.get(adyActual.obtenerNombreAdyacente()).obtenerAdy();
					//aca tal vez habra que definir el operador == para Arista:
					Arista ciudadActual = new Arista(ciudad.obtenerNombre(),adyActual.obtenerPesoTolerado());
					adyAdyActual.remove(ciudadActual);
				}		
			}
			
		return adyacencias.get(ciudadDestino).obtenerPesoHastaAqui();
		
		}
	
	
		public void generarCiudades(ArrayList<Vecindad> Vecindades) { //O(E)
		   
		      for( Vecindad Vecindad: Vecindades ) {
		    	  
		         Ciudad ciudad1 = damevecino2(adyacencias, Vecindad.ObtenerCiudad1() ); 
		         Ciudad ciudad2 = damevecino2(adyacencias, Vecindad.ObtenerCiudad2() ); 
		         
		         ciudad1.obtenerAdy().add( new Arista (Vecindad.ObtenerCiudad2(), Vecindad.obtenerPesoEntreCiudades()));
		         ciudad2.obtenerAdy().add( new Arista (Vecindad.ObtenerCiudad1(), Vecindad.obtenerPesoEntreCiudades()));
		           
		      }  
		}
	
	 public Ciudad damevecino2(HashMap<String, Ciudad> adyacen, String vecino) {
		 
	      if (!adyacen.containsKey( vecino)) { //containsKey llama a getEntry(vecino) y lo compara con NULL. 
	    	  Ciudad nuevaCiudad = new Ciudad(vecino);
	          adyacen.put(vecino, nuevaCiudad);
	      }
	      
	      
	      return (Ciudad)(adyacen.get(vecino));
	            
	   }
	    
	
	public static ArrayList<Vecindad> ParseAVecinos(ArrayList<String> vecindades){ //O(E)
		
		   ArrayList<Vecindad> res = new ArrayList<Vecindad>();
		   for(int i=0; i<vecindades.size(); i+=3){
		      String vecino1 = vecindades.get(i);
		      String vecino2 = vecindades.get(i+1);
		      int peso_entre_ellos = Integer.parseInt(vecindades.get(i+2));
		      res.add(new Vecindad(vecino1, vecino2, peso_entre_ellos));
		   }
		   return res;
		}
	
}


